package com.sheng.leetcode.year2022.month06.day09;

import org.junit.Test;

import java.util.Random;

/**
 * @author liusheng
 * @date 2022/06/09
 *
 * 497. 非重叠矩形中的随机点
 *
 * 给定一个由非重叠的轴对齐矩形的数组 rects ，
 * 其中 rects[i] = [ai, bi, xi, yi] 表示 (ai, bi) 是第 i 个矩形的左下角点，
 * (xi, yi) 是第 i 个矩形的右上角点。设计一个算法来随机挑选一个被某一矩形覆盖的整数点。
 * 矩形周长上的点也算做是被矩形覆盖。所有满足要求的点必须等概率被返回。
 * 在给定的矩形覆盖的空间内的任何整数点都有可能被返回。
 * 请注意 ，整数点是具有整数坐标的点。
 *
 * 实现 Solution 类:
 *
 * Solution(int[][] rects) 用给定的矩形数组 rects 初始化对象。
 * int[] pick() 返回一个随机的整数点 [u, v] 在给定的矩形所覆盖的空间内。
 *
 * 示例 1：
 *
 * 输入:
 * ["Solution", "pick", "pick", "pick", "pick", "pick"]
 * [[[[-2, -2, 1, 1], [2, 2, 4, 6]]], [], [], [], [], []]
 * 输出:
 * [null, [1, -2], [1, -1], [-1, -2], [-2, -2], [0, 0]]
 *
 * 解释：
 * Solution solution = new Solution([[-2, -2, 1, 1], [2, 2, 4, 6]]);
 * solution.pick(); // 返回 [1, -2]
 * solution.pick(); // 返回 [1, -1]
 * solution.pick(); // 返回 [-1, -2]
 * solution.pick(); // 返回 [-2, -2]
 * solution.pick(); // 返回 [0, 0]
 *
 * 提示：
 *
 * 1 <= rects.length <= 100
 * rects[i].length == 4
 * -109 <= ai < xi <= 109
 * -109 <= bi < yi <= 109
 * xi - ai <= 2000
 * yi - bi <= 2000
 * 所有的矩形不重叠。
 * pick 最多被调用 104 次。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/random-point-in-non-overlapping-rectangles
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0497 {

    @Test
    public void test01(){
//        int[][] rects = {{-2, -2, 1, 1}, {2, 2, 4, 6}};
        int[][] rects = {{82918473, -57180867, 82918476, -57180863},
                {83793579, 18088559, 83793580, 18088560},
                {66574245, 26243152, 66574246, 26243153},
                {72983930, 11921716, 72983934, 11921720}};
        Solution solution = new Solution(rects);
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
        solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();solution.pick();
    }

}
class Solution {

    private int[][] rects;

    public Solution(int[][] rects) {
        this.rects = rects;
    }

    public int[] pick() {
        //ai，bi即可看为矩形的起始坐标点，求除矩形的长宽
        //i为随机到的哪个矩形，每个矩形的大小不一样，权重不同，不能直接随机
        //int i = new Random().nextInt(rects.length);
        int area_sum = 0;
        int[] selected = new int[4];
        for (int[] rect : rects) {
            int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
            area_sum += area;
            if (new Random().nextInt(Integer.MAX_VALUE) % area_sum < area) {
                selected = rect;
            }
        }
        //x坐标的长度
        int wid = selected[2] - selected[0];
        //y坐标的长度
        int lon = selected[3] - selected[1];
//        int i1 = new Random().nextInt(wid + 1) + rects[i][0];
//        int i2 = new Random().nextInt(lon + 1) + rects[i][1];
//        System.out.println(i1 + "~~" + i2);
//        return new int[]{i1, i2};
        return new int[]{new Random().nextInt(wid + 1) + selected[0], new Random().nextInt(lon + 1) + selected[1]};
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(rects);
 * int[] param_1 = obj.pick();
 */

//class Solution {
//
//    public Solution(int[][] rects) {
//        _rects = rects;
//    }
//
//    public int[] pick() {
//        int area_sum = 0;
//        Random rand = new Random();
//        int[] selected = new int[4];
//        for(int[] rect : _rects){
//            int area = (rect[2] - rect[0] + 1) * (rect[3] - rect[1] + 1);
//            area_sum += area;
//            if(rand.nextInt(Integer.MAX_VALUE) % area_sum < area) selected = rect;
//        }
//        int x = rand.nextInt(Integer.MAX_VALUE) % (selected[2] - selected[0] + 1) + selected[0];
//        int y = rand.nextInt(Integer.MAX_VALUE) % (selected[3] - selected[1] + 1) + selected[1];
//        return new int[]{x, y};
//    }
//
//    private int[][] _rects;
//}

//这是一个相对来说没有固定输出的题目，随机点落在哪个矩形中的概率和矩形大小成正比，
//因此我们需要在计算矩形面积的大小，对应一个概率值，然后用一个rand函数来生成一个随机数，
//看看落在哪个区间，然后选择相应的矩形，在这个矩形内再随机选点。
//看了网上的一个题解，用area_sum记录所有矩形的面积总和，当然这个值在我们计算矩形面积的过程中会不断更新，
//然后每当我们计算一个矩形面积，我们先将area加到area_sum中，然后用rand()%area_sum和area作比较，
//如果小于这个area，我们就默认这个area是我们最后选定的矩形。为什么这样计算？其实这种方法和上面提到的每个矩形对应一个概率区间，
//然后再用随机数来选区间的方法是一样的，rand()%area_sum就是一个位于[0,area_sum]之间的数，我们把area_sum想象成一条线型区间，
//当前计算的矩形面积是area，相当于占据了前面area的区间长度，如果rand()%area_sum处于这个区间内，我们就选择当前这个矩形，
//这其实就是在计算它的概率值。rand()的每个输出之间相互没有影响，因此我们无论调用一次还是多次，
//最终选择哪个区间都是根据他们的面积大小也就是概率值来决定的，因此可以用上面那种方法。
